#include <vector>
#include <algorithm>
using namespace std;
/*
 * @lc app=leetcode.cn id=31 lang=cpp
 *
 * [31] 下一个排列
 */

// @lc code=start
class Solution {
public:
    // 1 5 8 4 7 6 5 3 1
    void nextPermutation(vector<int>& nums) {
        int last = nums.size() - 1;
        while (last > 0 && nums[last] <= nums[last - 1]) last--;
        if (last > 0) { 
            int target = nums.size() - 1;
            while (target > last && nums[target] <= nums[last - 1]) target--;
            swap(nums[target], nums[last - 1]);
        }
        for (int i = last, j = nums.size() - 1; i < j; i++, j--) {
            swap(nums[i], nums[j]);
        }
    } 
};
// @lc code=end

